package com.foxzzz.dynamic.programming;

public class Solution343 {
    public int integerBreak1(int n) {
        if (n == 2)
            return 1;
        else if (n == 3)
            return 2;
        else if (n == 4)
            return 4;
        else if (n % 3 == 0) {
            return (int) Math.pow(3, n / 3);
        } else if (n % 3 == 1) {
            return (int) Math.pow(3, n / 3 - 1) * 4;
        } else if (n % 3 == 2) {
            return (int) Math.pow(3, n / 3) * 2;
        } else {
            return 0;
        }
    }

    public int integerBreak(int n) {
        if (n <= 3)
            return n - 1;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for (int i = 4; i <= n; i++) {
            for (int j = 1; j <= i / 2; j++) {

               dp[i]=Math.max(dp[i],dp[i-j]*dp[j]);
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        boolean pass=true;
        Solution343 solution343=new Solution343();
        for (int i = 2; i < 100; i++) {
            if(solution343.integerBreak(i)!=solution343.integerBreak1(i)){
                System.out.println(i);
                System.out.println(solution343.integerBreak(i)+"---"+solution343.integerBreak1(i));
                break;
            }
        }

    }
}
